#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 80;
const int M = 1<<13;
const int mod = 998244353;
const int inv2 = (mod+1) / 2;

ll mat[N][N][M],r[N][N],c[M];
int n,m,w;
char s[32];

ll qp(ll x,int t){ll res=1;for(;t;t>>=1,x=x*x%mod)if(t&1)res=res*x%mod;return res;}

void FWT(ll *f,int len,int on = 1){
	for(int h = 2,cnt = 0;h <= len;h <<= 1,cnt++)
		for(int i = 0,j = h>>1;i < len;i += h)
			for(int k = i;k < i + j;k++)
				if(s[cnt] == '|')
					f[k+j] = (f[k+j] + f[k] * on % mod + mod) % mod;
				else if(s[cnt] == '&')
					f[k] = (f[k] + f[k+j] * on % mod + mod) % mod;
				else if(s[cnt] == '^'){
					ll u = f[k],v = f[k + j];
					f[k] = (u + v) % mod,f[k + j] = (u - v + mod) % mod;
					if(on == -1) f[k] = 1ll * f[k] * inv2 % mod,f[k + j] = 1ll * f[k + j] * inv2 % mod;
				}
}

int Guess(){
	ll ans = 1;
	for(int i = 1,j;i < n;i++){
		for(j = i;j < n;j++) if(r[j][i]) break;
		if(j >= n) return 0;
		if(j != i) ans = - ans , swap(r[i],r[j]);
		ll inv = qp(r[i][i],mod-2);
		for(j = i+1;j < n;j++)
			if(r[j][i]){
				ll t = r[j][i] * inv % mod;
				for(int k = i;k < n;k++) r[j][k] = (r[j][k] - r[i][k] * t % mod + mod) % mod;
			}
	}
	for(int i = 1;i < n;i++) ans = ans * r[i][i] % mod; return (ans + mod) % mod;
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in;
	scanf("%s",s); w = strlen(s);
	for(int i = 1,x,y,v;i <= m;i++){
		x = in,y = in,v = in;
		mat[x][y][v] = (mat[x][y][v] - 1 + mod) % mod; mat[y][x][v] = (mat[y][x][v] -1 + mod) % mod;
		mat[x][x][v] = (mat[x][x][v] + 1) % mod; mat[y][y][v] = (mat[y][y][v] + 1) % mod;
	}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
			FWT(mat[i][j],1<<w);
	for(int val = 0;val < 1 << w;val++){
		memset(r,0,sizeof(r));
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= n;j++)
				r[i][j] = mat[i][j][val];
		c[val] = Guess();
	}
	FWT(c,1<<w,-1);
	for(int i = (1 << w) - 1;i >= 0;i--) if(c[i] > 0) return printf("%d\n",i),0;
	return printf("-1\n"),0;
}
